A scheduler such as a priority queue is typically used for the cases where the operation order of a number of elements is sorted based on their time stamps in the packet-switching networks. Elements can be any kind of entities such as virtual path connections and virtual channel connections in a broadband network. Each time the element with the smallest/earliest time stamp is scheduled to obtain the control of some kinds of crucial resources such as transmission line in the packet-switching networks.
The binary time stamp has to be long enough such that any two time stamps in the system are comparable, i.e., the precision should cover the possible time stamp overflow in the worst case. In many packet-switching networks, this would require 32-bit binary representation. Regular floating-point representation cannot be used for the time stamp due to the precision lost. Considering that there are tens of thousands of elements in the networks, the internal and external storage to store the time stamps is extremely costly.
The system in the packet-switching networks usually maintains a global virtual clock as the scheduling reference. Each element has a time interval/rate to specify the bandwidth it requests. As an example, by ATM Forum definition, the rate/time interval is represented as a floating-point consisting of 10-bit mantissa and 5-bit exponent. The time stamp for element i is increased as follows: ##EQU1## where j is a positive integer and i is a positive integer.
The scheduler usually tries to schedule the elements on time according to their time stamps. Too early or too late might not guarantee Quality of Services and cause other system problems such as buffer overflow. A good service discipline can guarantee an element will be served no later and no earlier than a given upper bound depending on the applications.
The purpose of the present invention is to use a window-based number to encode the time stamp. The proposed compressed number should not cause any precision lost and the encoding/decoding mechanism should be straightforward and easy to implement. The window-based time stamp can dramatically reduce the amount of storage. The present invention could work as the coprocessor and preprocessor of any kinds of scheduler which can guarantee the service delay bound on the elements.